package com.lisp.algorithm.test.sort;

import java.util.Arrays;

public class HeapSort {
	
	public static void main(String[] args) {
		int data[] = {10, 1, 9, 45, 90, 76, 8, 29, 28, 43, 2, 7, 9, 190, 9, 9};
		buildMaxHeap(data);
		System.out.println(Arrays.toString(data));
		for(int i=data.length-1; i>0; i--) {
			int tmp = data[0];
			data[0] = data[i];
			data[i] = tmp;

			maxHeapify(0, data, i);
		}
		
		System.out.println(Arrays.toString(data));
	}
	
	private static void buildMaxHeap(int data[]) {
		for(int i=data.length/2-1; i>=0; i--) {
			maxHeapify(i, data, data.length);
		}
	}

	private static void maxHeapify(int i, int[] data, int heapSize) {
		int maxIndex = i;
		int left = left(i);
		if(left < heapSize && data[left] > data[i]) {
			maxIndex = left;
		}
		
		int right = left + 1;
		if(right < heapSize && data[right] > data[maxIndex]) {
			maxIndex = right;
		}
		
		if(maxIndex != i) {
			int tmp = data[i];
			data[i] = data[maxIndex];
			data[maxIndex] = tmp;
			
			maxHeapify(maxIndex, data, heapSize);
		}
	}
	
	private static int left(int i) {
		return i*2 + 1;
	}
}
